## 二维dp数组
class Selution(object):
    def backpack2(self, bag_weight, weight, value):

        dp = [[0]*(bag_weight+1) for _ in range(len(weight))]

        for j in range(weight[0], bag_weight+1):
            dp[0][j] = value[0] + dp[0][j-weight[0]]

        for i in range(len(weight)):
            for j in range(1, bag_weight+1):
                if weight[i]<j:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], value[i]+dp[i][j-weight[i]])

        return dp[-1][-1]
    

## 一维dp数组
class Selution(object):
    def backpack2(self, bag_weight, weight, value):

        dp = [0]*(bag_weight+1)

        for i in range(len(weight)):
            for j in range(weight[i], bag_weight+1):
                dp[j] = max(dp[j], value[i]+dp[j-weight[i]])
        return dp[-1]